1.1 Field of the Invention
The invention concerns systems in general in which operation of the system is subject to constraints and particularly concerns constraints involved in maintaining the integrity of data in a data base system.
1.2 Description of the Prior Art
An important operation in data base systems is changing the data in the system. Operations which change data may involve adding data, deleting data, or updating data, which is a combination of deleting and adding. In the following, operations which change the data base are termed generally update operations.
Care must be taken in an update operation that the data being added to the data base system does not compromise the integrity of the data in the data base system. For example, a data base of employee information may have a record for each employee which includes fields specifying the employee's grade and pay. Pay may be coupled to the grade, so that it must be above a minimum and below a maximum specified for the grade. In such a data base, maintaining the integrity of the data base system requires that when a new employee record is added or an existing record is altered, the data base system check whether the pay in the new or altered record is within the range specified for the grade. A condition which must be met by data which is to be included in a data base in order to maintain the integrity of the data base is termed a constraint, and in many data base systems, any update operation includes a phase called constraint checking, in which the data base system determines whether the constraints required for the operation are satisfied.
One way of doing constraint checking is to do the operation, check any constraints, and if a constraint has been violated, undo the update. However, it is usually possible to determine whether the constraints will be violated before the update is made and do the update only if there is no violation.
Of course, constraint checking takes time, so it is important to do as little as possible of it. In many cases, constraints are dependent on other constraints in such a fashion that only a few of the constraints actually need to be checked. A smaller set of constraints which can be checked with the same results as checking all of the constraints is termed an update constraint. One way of finding an update constraint is to calculate a logical formula called the weakest precondition of the entire set of constraints with regard to the update. The weakest precondition sets forth a set of constraints which must be true if the entire set of constraints is to be true after the update has been performed. See C. A. R. Hoare, "An axiomatic basis for computer programming," in: Communications of the ACM 12(10), October 1969.
However, even testing the constraints of the weakest precondition may involve more work than necessary. As set forth in X. Qian, "An effective method for integrity constraint simplification", in: Fourth International Conference on Data Engineering, 1988, it is possible to take advantage of the fact that the constraints are known to hold in advance. Since that is the case, the weakest precondition can be factored into a first portion of the weakest precondition which is implied by the constraints and a second portion which is not. The AND of these portions is logically equivalent to the weakest pre-condition, and consequently, it possible to check the weakest precondition by checking the second portion only, and the second portion by itself can thus function as the update constraint.
A problem with the foregoing work on update constraints involving the weakest precondition and Qian's further simplification thereof is that it does not take into account the fact that in practical data base systems, certain of the data base system operations which are executed in the course of an update operation may themselves abort, that is, they may terminate without affecting the data base if certain constraints imposed by the data base system are not satisfied. For example, the data base system insert operation which actually inserts a new record into a data base requires that the new record be in fact new; it determines this by checking whether a key which identifies the record to the date base system is the same as that of any existing record in the data base; if it is, the insert operation aborts. The constraints which these operations must satisfy are different from those required to keep the content of the data consistent, and it has heretofore not been apparent how to incorporate such constraints into update constraints.